#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// 实现功能

vector<vector<int>> threeNumberSum(
  vector<int> array, int targetSum) {
  // [12, 3, 1, 2, -6, 5, -8, 6]
  sort(array.begin(), array.end());
  // [-8, -6, 1, 2, 3, 5, 6, 12]


  vector<vector<int>> result {};

  for (int i = 0; i <= array.size() - 3; ++i) {
    int left = i + 1;
    int right = array.size() - 1;

    while (left < right) {
      int sum = array[i] + array[left] + array[right];

      if (sum == targetSum) {
        result.push_back({array[i], array[left], array[right]});
        ++left;
        --right;
      }
      else if (sum < targetSum) { ++left; }
      else { --right; }
    }
  }

  return result;
}

int main(int argc, char const *argv[]){
  vector<int> arr {12, 3, 1, 2, -6, 5, -8, 6};

  auto result = threeNumberSum(arr, 0);

  for (auto answer : result) {
    for (auto n : answer) { // vector<int>
      cout<<n<<" ";
    }

    cout<<endl;
  }
  return 0;
}

